/*
 * @lc app=leetcode.cn id=864 lang=cpp
 *
 * [864] 获取所有钥匙的最短路径
 */

// @lc code=start
class Solution
{
public:
    struct node
    {
        int x, y, step, status;
    };

    int n, m, cnt, mark[35][35][256] = {0};
    int dir[4][2] = {0, 1, 1, 0, 0, -1, -1, 0};
    int b2[10] = {1, 2, 4, 8, 16, 32, 64, 128, 256};

    int shortestPathAllKeys(vector<string> &mmap)
    {
        n = mmap.size(), m = mmap[0].size();
        queue<node> que;
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < m; j++)
            {
                if (mmap[i][j] == '@')
                {
                    mmap[i][j] = '.';
                    que.push((node){i, j, 0, 0});
                    mark[i][j][0] = 1;
                }
                else if (mmap[i][j] >= 'a' && mmap[i][j] <= 'z')
                {
                    cnt++;
                }
            }
        }
        while (!que.empty())
        {
            node temp = que.front();
            que.pop();
            if (temp.status == b2[cnt] - 1)
            {
                return temp.step;
            }
            for (int i = 0; i < 4; i++)
            {
                int x = temp.x + dir[i][0];
                int y = temp.y + dir[i][1];
                if (x < 0 || y < 0 || x == n || y == m || mark[x][y][temp.status])
                {
                    continue;
                }
                if (mmap[x][y] == '.')
                {
                    mark[x][y][temp.status] = 1;
                    que.push((node){x, y, temp.step + 1, temp.status});
                }
                else if (mmap[x][y] >= 'a' && mmap[x][y] <= 'z')
                {
                    mark[x][y][temp.status] = 1;
                    mark[x][y][temp.status | b2[mmap[x][y] - 'a']] = 1;
                    que.push((node){x, y, temp.step + 1, temp.status | b2[mmap[x][y] - 'a']});
                }
                else if (mmap[x][y] >= 'A' && mmap[x][y] <= 'Z' && (temp.status & b2[mmap[x][y] - 'A']))
                {
                    mark[x][y][temp.status] = 1;
                    que.push((node){x, y, temp.step + 1, temp.status});
                }
            }
        }
        return -1;
    }
};
// @lc code=end
